<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1">
    <meta name="keywords" content="Hexo Theme Redefine">
    
    <meta name="author" content="雲之残骸">
    <!-- preconnect -->
    <link rel="preconnect" href="https://fonts.googleapis.com">
    <link rel="preconnect" href="https://fonts.gstatic.com" crossorigin>
    
    
    <!--- Seo Part-->
    
    <link rel="canonical" href="https://wreckloud.github.io/2023/09/17/数据结构与基础-c语言/"/>
    <meta name="robots" content="index,follow">
    <meta name="googlebot" content="index,follow">
    <meta name="revisit-after" content="1 days">
    
        <meta name="description" content="数据结构的老师真的讲的太拉了...实在不行了.只能去网上找视频看看,听说数据结构还挺重要的.">
<meta property="og:type" content="article">
<meta property="og:title" content="数据结构与算法(c语言)">
<meta property="og:url" content="https://wreckloud.github.io/2023/09/17/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E5%9F%BA%E7%A1%80-c%E8%AF%AD%E8%A8%80/index.html">
<meta property="og:site_name" content="赛博狼窝">
<meta property="og:description" content="数据结构的老师真的讲的太拉了...实在不行了.只能去网上找视频看看,听说数据结构还挺重要的.">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="2023-09-17T11:02:37.000Z">
<meta property="article:modified_time" content="2023-09-24T13:22:58.860Z">
<meta property="article:author" content="Wreckloud">
<meta property="article:tag" content="学习笔记">
<meta name="twitter:card" content="summary">
    
    
    <!--- Icon Part-->
    <link rel="icon" type="image/png" href="/images/web.png" sizes="192x192">
    <link rel="apple-touch-icon" sizes="180x180" href="/images/web.png">
    <meta name="theme-color" content="#A31F34">
    <link rel="shortcut icon" href="/images/web.png">
    <!--- Page Info-->
    
    <title>
        
            数据结构与算法(c语言) -
        
        赛博狼窝
    </title>
    
<link rel="stylesheet" href="/css/style.css">


    
        
<link rel="stylesheet" href="/css/build/styles.css">

    

    
<link rel="stylesheet" href="/fonts/fonts.css">

    
<link rel="stylesheet" href="/fonts/Satoshi/satoshi.css">

    
<link rel="stylesheet" href="/fonts/Chillax/chillax.css">

    <!--- Font Part-->
    
    
        <link href="" rel="stylesheet">
    
    
    

    <!--- Inject Part-->
    
    <script id="hexo-configurations">
    let Global = window.Global || {};
    Global.hexo_config = {"hostname":"wreckloud.github.io","root":"/","language":"zh-CN","path":"search.xml"};
    Global.theme_config = {"articles":{"style":{"font_size":"16px","line_height":1.5,"image_border_radius":"4px","image_alignment":"center","image_caption":true,"link_icon":true},"word_count":{"enable":true,"count":true,"min2read":true},"author_label":{"enable":true,"auto":false,"list":[]},"code_block":{"copy":false,"style":"simple","font":{"enable":"ture","family":null,"url":null}},"toc":{"enable":true,"max_depth":3,"number":false,"expand":true,"init_open":true},"copyright":false,"lazyload":true,"recommendation":{"enable":false,"title":"推荐阅读","limit":3,"mobile_limit":2,"placeholder":"/images/wallhaven-wqery6-light.webp","skip_dirs":[]}},"colors":{"primary":"#A31F34","secondary":null},"global":{"fonts":{"chinese":{"enable":false,"family":null,"url":null},"english":{"enable":false,"family":null,"url":null}},"content_max_width":"1000px","sidebar_width":"210px","hover":{"shadow":true,"scale":false},"scroll_progress":{"bar":false,"percentage":true},"website_counter":{"url":"https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js","enable":false,"site_pv":true,"site_uv":true,"post_pv":true},"single_page":true,"open_graph":true,"google_analytics":{"enable":false,"id":null}},"home_banner":{"enable":true,"style":"fixed","image":{"light":"/images/wallhaven-wqery6-light.webp","dark":"/images/wallhaven-wqery6-dark.webp"},"title":"今天也要好心情!","subtitle":{"text":["正在加载..."],"hitokoto":{"enable":"ture","api":"https://v1.hitokoto.cn"},"typing_speed":130,"backing_speed":80,"starting_delay":1500,"backing_delay":3000,"loop":false,"smart_backspace":true},"text_color":{"light":"#fff","dark":"#d1d1b6"},"text_style":{"title_size":"2.8rem","subtitle_size":"1.5rem","line_height":1.2},"custom_font":{"enable":false,"family":null,"url":null},"social_links":{"enable":false,"links":{"github":null,"instagram":null,"zhihu":null,"twitter":null,"bilibili":null},"qrs":{"weixin":null}}},"plugins":{"feed":{"enable":false},"aplayer":{"enable":false,"type":"fixed","audios":[{"name":null,"artist":null,"url":null,"cover":null}]},"mermaid":{"enable":true,"version":"9.3.0"}},"version":"2.4.4","navbar":{"auto_hide":false,"color":{"left":"#f78736","right":"#367df7","transparency":35},"links":{"Home":{"path":"/","icon":"fa-solid fa-house"},"tags":{"path":"/tag/","icon":"fa-solid fa-tags"},"Status":{"path":"/masonry/","icon":"fa-solid fa-sparkles"},"About":{"icon":"fa-solid fa-feather","submenus":{"关于我":"/about/","我的b站":"https://space.bilibili.com/177822535?spm_id_from=333.1007.0.0"}}},"search":{"enable":true,"preload":true}},"page_templates":{"friends_column":2,"tags_style":"blur"},"home":{"sidebar":{"enable":true,"position":"left","first_item":"info","announcement":"欢迎朋友们参观!  不过刚刚搭好现在还没什么内容呢...","links":null},"article_date_format":"auto","categories":{"enable":true,"limit":3},"tags":{"enable":true,"limit":3}},"footerStart":"2023/9/17 14:00:00"};
    Global.language_ago = {"second":"%s 秒前","minute":"%s 分钟前","hour":"%s 小时前","day":"%s 天前","week":"%s 周前","month":"%s 个月前","year":"%s 年前"};
    Global.data_config = {"masonry":true};
  </script>
    
    <!--- Fontawesome Part-->
    
<link rel="stylesheet" href="/fontawesome/fontawesome.min.css">

    
<link rel="stylesheet" href="/fontawesome/brands.min.css">

    
<link rel="stylesheet" href="/fontawesome/solid.min.css">

    
<link rel="stylesheet" href="/fontawesome/regular.min.css">

    
    
    
    
<meta name="generator" content="Hexo 6.3.0"></head>


<body>
<div class="progress-bar-container">
    

    
        <span class="pjax-progress-bar"></span>
        <span class="swup-progress-icon">
            <i class="fa-solid fa-circle-notch fa-spin"></i>
        </span>
    
</div>


<main class="page-container" id="swup">

    

    <div class="main-content-container">


        <div class="main-content-header">
            <header class="navbar-container">
    
    <div class="navbar-content">
        <div class="left">
            
            <a class="logo-title" href="https://wreckloud.github.io/">
                
                赛博狼窝
                
            </a>
        </div>

        <div class="right">
            <!-- PC -->
            <div class="desktop">
                <ul class="navbar-list">
                    
                        
                            <li class="navbar-item">
                                <!-- Menu -->
                                <a class="" 
                                    href="/"  >
                                    
                                        
                                            <i class="fa-solid fa-house"></i>
                                        
                                        首页
                                    
                                </a>
                                <!-- Submenu -->
                                
                            </li>
                    
                        
                            <li class="navbar-item">
                                <!-- Menu -->
                                <a class="" 
                                    href="/tag/"  >
                                    
                                        
                                            <i class="fa-solid fa-tags"></i>
                                        
                                        标签
                                    
                                </a>
                                <!-- Submenu -->
                                
                            </li>
                    
                        
                            <li class="navbar-item">
                                <!-- Menu -->
                                <a class="" 
                                    href="/masonry/"  >
                                    
                                        
                                            <i class="fa-solid fa-sparkles"></i>
                                        
                                        画廊
                                    
                                </a>
                                <!-- Submenu -->
                                
                            </li>
                    
                        
                            <li class="navbar-item">
                                <!-- Menu -->
                                <a class="has-dropdown" 
                                    href="#" onClick="return false;">
                                    
                                        
                                            <i class="fa-solid fa-feather"></i>
                                        
                                        关于&nbsp;<i class="fa-solid fa-chevron-down"></i>
                                    
                                </a>
                                <!-- Submenu -->
                                
                                    <ul class="sub-menu">
                                    
                                        <li>
                                        <a href="/about/">关于我
                                        </a>
                                        </li>
                                    
                                        <li>
                                        <a target="_blank" rel="noopener" href="https://space.bilibili.com/177822535?spm_id_from=333.1007.0.0">我的B站
                                        </a>
                                        </li>
                                    
                                    </ul>
                                
                            </li>
                    
                    
                        <li class="navbar-item search search-popup-trigger">
                            <i class="fa-solid fa-magnifying-glass"></i>
                        </li>
                    
                </ul>
            </div>
            <!-- Mobile -->
            <div class="mobile">
                
                    <div class="icon-item search search-popup-trigger"><i class="fa-solid fa-magnifying-glass"></i></div>
                
                <div class="icon-item navbar-bar">
                    <div class="navbar-bar-middle"></div>
                </div>
            </div>
        </div>
    </div>

    <!-- Mobile drawer -->
    <div class="navbar-drawer w-full absolute top-0 left-0 bg-background-color">
        <ul class="drawer-navbar-list flex flex-col justify-start items-center">
            
                
                    <li class="drawer-navbar-item text-base my-1.5 flex justify-center items-center">
                        <a class="rounded-3xl py-1.5 px-5 hover:border hover:!text-primary active:!text-primary group " 
                        href="/"  >
                             
                                
                                    <i class="fa-solid fa-house"></i>
                                
                                首页
                            
                        </a>
                    </li>
                    <!-- Submenu -->
                    
            
                
                    <li class="drawer-navbar-item text-base my-1.5 flex justify-center items-center">
                        <a class="rounded-3xl py-1.5 px-5 hover:border hover:!text-primary active:!text-primary group " 
                        href="/tag/"  >
                             
                                
                                    <i class="fa-solid fa-tags"></i>
                                
                                标签
                            
                        </a>
                    </li>
                    <!-- Submenu -->
                    
            
                
                    <li class="drawer-navbar-item text-base my-1.5 flex justify-center items-center">
                        <a class="rounded-3xl py-1.5 px-5 hover:border hover:!text-primary active:!text-primary group " 
                        href="/masonry/"  >
                             
                                
                                    <i class="fa-solid fa-sparkles"></i>
                                
                                画廊
                            
                        </a>
                    </li>
                    <!-- Submenu -->
                    
            
                
                    <li class="drawer-navbar-item text-base my-1.5 flex justify-center items-center">
                        <a class="rounded-3xl py-1.5 px-5 hover:border hover:!text-primary active:!text-primary group has-dropdown" 
                        href="#" onClick="return false;">
                            
                                
                                    <i class="fa-solid fa-feather"></i>
                                
                                关于&nbsp;<i class="group-hover:rotate-180 transition-transform fa-solid fa-chevron-down"></i>
                            
                        </a>
                    </li>
                    <!-- Submenu -->
                              
                        
                            <li class="text-base flex justify-center items-center hover:underline active:underline hover:underline-offset-1 rounded-3xl">
                                <a class="py-0.5" href="/about/">关于我</a>
                            </li>
                        
                            <li class="text-base flex justify-center items-center hover:underline active:underline hover:underline-offset-1 rounded-3xl">
                                <a class="py-0.5" target="_blank" rel="noopener" href="https://space.bilibili.com/177822535?spm_id_from=333.1007.0.0">我的B站</a>
                            </li>
                        
                    
            

        </ul>
    </div>

    <div class="window-mask"></div>

</header>


        </div>

        <div class="main-content-body">

            

            <div class="main-content">

                
                    <div class="post-page-container">
    <div class="article-content-container">

        <div class="article-title">
            
                
                
                <img src="/../img/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E5%9F%BA%E7%A1%80%E5%B0%81%E9%9D%A2.jpg" alt="数据结构与算法(c语言)" class="max-w-none"/>
                
                <h1 class="article-title-cover">数据结构与算法(c语言)</h1>
            
            </div>
            
                    
        
        
            <div class="article-header">
                <div class="avatar">
                    <img src="/images/default.png">
                </div>
                <div class="info">
                    <div class="author">
                        <span class="name">雲之残骸</span>
                        
                            <span class="author-label">Lv1</span>
                        
                    </div>
                    <div class="meta-info">
                        <div class="article-meta-info">
    <span class="article-date article-meta-item">
        <i class="fa-regular fa-pen-fancy"></i>&nbsp;
        <span class="desktop">2023-09-17 19:02:37</span>
        <span class="mobile">2023-09-17 19:02:37</span>
        <span class="hover-info">创建</span>
    </span>
    
        <span class="article-date article-meta-item">
            <i class="fa-regular fa-wrench"></i>&nbsp;
            <span class="desktop">2023-09-24 21:22:58</span>
            <span class="mobile">2023-09-24 21:22:58</span>
            <span class="hover-info">更新</span>
        </span>
    

    
    
        <span class="article-tags article-meta-item">
            <i class="fa-regular fa-tags"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/tags/%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/">学习笔记</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    

    
    
        <span class="article-wordcount article-meta-item">
            <i class="fa-regular fa-typewriter"></i>&nbsp;<span>1.7k 字</span>
        </span>
    
    
        <span class="article-min2read article-meta-item">
            <i class="fa-regular fa-clock"></i>&nbsp;<span>6 分钟</span>
        </span>
    
    
</div>

                    </div>
                </div>
            </div>
        

        


        <div class="article-content markdown-body">
            <p>上课老师真的好无聊,还是上b站自学吧,听说这门课还挺难学习的?<br>笔记源自于这套课程:<br><a class="link"   target="_blank" rel="noopener" href="https://www.bilibili.com/video/BV1jW411K7yg/?spm_id_from=333.337.search-card.all.click" >C语言描述《数据结构和算法》 <i class="fa-regular fa-arrow-up-right-from-square fa-sm"></i></a># 第一章 绪论</p>
<h1 id="第一章-绪论"><a href="#第一章-绪论" class="headerlink" title="第一章 绪论"></a>第一章 绪论</h1><blockquote>
<p>不得不说我们老师讲的是真不行,说的话总是有很多完全没必要的句子,得不到她要说的重点</p>
</blockquote>
<h2 id="什么是数据结构"><a href="#什么是数据结构" class="headerlink" title="什么是数据结构"></a>什么是数据结构</h2><blockquote>
<p><strong>程序设计 &#x3D; 数据结构 + 算法</strong>  </p>
</blockquote>
<p>就是数据与元素的<strong>关系集合</strong></p>
<hr>
<p>传统上,数据结构分为<strong>逻辑结构</strong>和<strong>物理结构</strong>。   </p>
<p><strong>1. 逻辑结构</strong> </p>
<p>逻辑结构是指数据对象中数据元素之间的相互关系。<br>逻辑结构又分为:集合结构、线性结构、树形结构和图形结构  </p>
<p><strong>2. 物理结构</strong></p>
<p>物理结构是指数据的逻辑结构在计算机中的存储形式(一般说的是内存)。<br>物理结构又分为顺序存储和链式存储</p>
<h2 id="什么是算法"><a href="#什么是算法" class="headerlink" title="什么是算法"></a>什么是算法</h2><p>顾名思义,就是计算的技巧和方式。<br>对于给定的问题,是可以由多个算法来解决。  </p>
<h2 id="算法的基本特征"><a href="#算法的基本特征" class="headerlink" title="算法的基本特征"></a>算法的基本特征</h2><p>算法的基本特征要：<br><strong>输入、输出、有穷性、确定性和可行性</strong>  </p>
<p>算法设计的要求有：<br><strong>正确性、可读性、健壮性、时间效率高和存储量低</strong></p>
<p>算法效率的度量方法:</p>
<ul>
<li>事后统计</li>
<li>事前分析</li>
</ul>
<p>影响程序运行时间的因素:</p>
<ul>
<li>算法的策略方案</li>
<li>问题的规模</li>
<li>编译器的质量</li>
<li>机器执行的速度</li>
</ul>
<h2 id="时间复杂度和空间复杂度"><a href="#时间复杂度和空间复杂度" class="headerlink" title="时间复杂度和空间复杂度"></a>时间复杂度和空间复杂度</h2><p>算法的时间复杂度的表示方式:</p>
<blockquote>
<p>$T(n) &#x3D; O(f(n))$<br>T(n):语句总的执行次数,是关于问题规模n的函数<br>f(n):问题规模n的某个函数<br>O( ):体现算法时间复杂度(大O记法)</p>
</blockquote>
<p>随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同<br>简单说就是:执行次数 &#x3D;&#x3D; 时间  </p>
<p>一般情况下,随着n的增大T(n)增长最慢的算法为最优算法.</p>
<p>算法的空间复杂度:</p>
<blockquote>
<p>$S(n) &#x3D; O(f(n))$</p>
</blockquote>
<p>通常,求”复杂度”是指时间复杂度</p>
<h1 id="第二章-线性表"><a href="#第二章-线性表" class="headerlink" title="第二章 线性表"></a>第二章 线性表</h1><h2 id="线性表的定义"><a href="#线性表的定义" class="headerlink" title="线性表的定义"></a>线性表的定义</h2><blockquote>
<p>ADT 线性表(List):由<strong>零个或多个</strong>数据元素组成的有限个有序数列.</p>
</blockquote>
<p>Data(数据元素):<br>存在多个元素时,中间元素有且只有一个前驱和一个后继</p>
<h2 id="抽象数据类型"><a href="#抽象数据类型" class="headerlink" title="抽象数据类型"></a>抽象数据类型</h2><p>整形,浮点,字符,这些都是数据类型<br>规定数据类型是为了适应各种不同计算条件的差异  </p>
<p>按照取值不同,数据类型可以分为两类:</p>
<ul>
<li>原子类型:不可以再分解的基本类型(整形、浮点型、字符型)</li>
<li>结构类型:由若干个类型组合而成(例如整型数组)</li>
</ul>
<p>抽象:抽取出事物具有的普遍性的本质</p>
<p><strong>抽象数据类型(Abstract Data type,ADT):</strong></p>
<p>抽象数据类型的标准格式:</p>
<div class="highlight-container" data-rel="C"><figure class="iseeu highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">ADT 抽象数据类型名称</span><br><span class="line"></span><br><span class="line">Data</span><br><span class="line">    数据元素之间逻辑关系的定义</span><br><span class="line">Operation</span><br><span class="line">    操作</span><br><span class="line"></span><br><span class="line">endADT        </span><br></pre></td></tr></table></figure></div>

<p><strong>线性表的抽象数据类型:</strong></p>
<p>Operation(操作符)</p>
<div class="highlight-container" data-rel="C"><figure class="iseeu highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">define</span> OK 1</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> ERROR 0</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> TRUE 1</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> FALSE 0</span></span><br></pre></td></tr></table></figure></div>

<ul>
<li>InitList(*L): 初始化操作,建立一个空的线性表L.</li>
<li>ListEmpty(L): 判断线性表是否为空表,若为空返回true.</li>
</ul>
<div class="highlight-container" data-rel="C"><figure class="iseeu highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">typedef</span> <span class="type">int</span> Status;</span><br><span class="line"></span><br><span class="line">Status <span class="title function_">GetElem</span><span class="params">(SqList L,<span class="type">int</span> i,ElemType *e)</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="keyword">if</span>(L.length==<span class="number">0</span>,<span class="type">int</span> i,ElemType *e)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">return</span> ERROR;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> OK;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></div>

<ul>
<li>ClearList(*L): 清空线性表L.</li>
<li>GetElem(L,i,*e): 将线性表L中的第i个位置元素值返回给e.</li>
<li>LocateElem(L,e): 在线性表L中查找和e相等的元素,若成功返回表中序号,否则返回0.</li>
<li>ListInsert(*L,i,e): 在线性表L中第i个位置插入新元素e.</li>
</ul>
<div class="highlight-container" data-rel="C"><figure class="iseeu highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line">Status <span class="title function_">ListInsert</span><span class="params">(SqList *L,<span class="type">int</span> i,ElemType e)</span></span><br><span class="line">&#123;</span><br><span class="line">  <span class="type">int</span> k;</span><br><span class="line"></span><br><span class="line">  <span class="keyword">if</span>(L-&gt;length == MAXSIZE)<span class="comment">//线性表满了</span></span><br><span class="line">  &#123;</span><br><span class="line">      <span class="keyword">return</span> ERROR;</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="keyword">if</span>(i&lt;<span class="number">1</span> || i&gt;L-&gt;length+<span class="number">1</span>)<span class="comment">//i不在范围内</span></span><br><span class="line">  &#123;</span><br><span class="line">      <span class="keyword">return</span> ERROR;</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="keyword">if</span>(i &lt;= L -&gt; length)</span><br><span class="line">  &#123;</span><br><span class="line">      <span class="keyword">for</span>(k=L-&gt;length<span class="number">-1</span>;k&gt;=i<span class="number">-1</span>;k--)</span><br><span class="line">      &#123;</span><br><span class="line">          L-&gt;data[k+<span class="number">1</span>] = L-&gt;data[k];</span><br><span class="line">      &#125;</span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line">  L-&gt;data[i<span class="number">-1</span>] = e;<span class="comment">//插入新元素</span></span><br><span class="line">  L-&gt;length++;</span><br><span class="line"></span><br><span class="line">  <span class="keyword">return</span> OK;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></div>

<ul>
<li>ListDelete(*L,i,*e): 删除线性表L中第i个位置元素,并用e返回其值.</li>
</ul>
<div class="highlight-container" data-rel="C"><figure class="iseeu highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line">Status <span class="title function_">ListDelete</span><span class="params">(SqList *L,<span class="type">int</span> i,ElemType *e)</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="type">int</span> k;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span>(L-&gt;length == <span class="number">0</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">return</span> ERROR;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(i&lt;<span class="number">1</span>||i&gt;L-&gt;length)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">return</span> ERROR;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    *e = L-&gt;data[i<span class="number">-1</span>];</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span>(i&lt;L-&gt;length)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">for</span>(k=i;k&lt;L-&gt;length:k++)</span><br><span class="line">        &#123;</span><br><span class="line">            L-&gt;data[k<span class="number">-1</span>]=L-&gt;data[k];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    L-&gt;length--;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> OK;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></div>

<ul>
<li>ListLength(L): 返回线性表L的元素个数.</li>
</ul>
<p>endADT</p>
<p>总结:<br>对于不同的应用,线性表的基本操作是不同的.</p>
<h2 id="线性表的顺序存储结构"><a href="#线性表的顺序存储结构" class="headerlink" title="线性表的顺序存储结构"></a>线性表的顺序存储结构</h2><p>顺序存储结构是用一段地址连续的存储单元一次存储线性表的数据元素<br>(类似于数组)</p>
<p>顺序存储结构代码:</p>
<div class="highlight-container" data-rel="C"><figure class="iseeu highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">define</span> MAXSIZE</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="type">int</span> ElemType;</span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">    ElemType data[MAXSIZE];</span><br><span class="line">    <span class="type">int</span> length;</span><br><span class="line">&#125;SqList;</span><br><span class="line"></span><br></pre></td></tr></table></figure></div>
<blockquote>
<ul>
<li>typedef是c语言的一个关键字,作用为给现有的数据类型取一个新名字  </li>
<li>结构体是一种复杂的数据类型,它可以将多个不同类型的数据组合成一个整体.<br>定义形式为:<br>struct 结构体名 {成员列表};</li>
<li>ElemType-通用类型(可以是任何类型)</li>
</ul>
</blockquote>
<p>顺序存储结构封装的三个属性:  </p>
<ol>
<li>存储空间<strong>起始</strong>位置:数组data</li>
<li>线性表的<strong>最大存储</strong>容量:数组长度MaxSize</li>
<li>线性表<strong>当前长度</strong>:length</li>
</ol>
<p>线性表的顺序存储结构中,存储、读取时,时间复杂度都是O(1).而在插入删除时都是O(n).<br>说明它<strong>更适合存取数据</strong>.</p>
<blockquote>
<p>优点:  </p>
<ul>
<li>无须额外增加存储空间.  </li>
<li>可以快速存取.</li>
</ul>
</blockquote>
<blockquote>
<p>缺点:  </p>
<ul>
<li>插入删除需要移动大量元素(最大缺陷)</li>
<li>线性表长度变化较大时,难以确定存储空间的容量</li>
<li>由于申请需要大块连续的空间,易造成小块碎片空间的浪费</li>
</ul>
</blockquote>
<h2 id="线性表的链式存储结构"><a href="#线性表的链式存储结构" class="headerlink" title="线性表的链式存储结构"></a>线性表的链式存储结构</h2><p>是针对插入删除优化的结果  </p>
<p>链式存储结构除了存储其本身的信息外,还存储一个指示其直接后继的存储位置信息.  </p>
<ul>
<li><strong>数据域</strong> :存储的元素信息</li>
<li><strong>指针域</strong> :存储直接后驱的位置信息</li>
<li><strong>存储映像</strong>:两部分的统称,也称作节点(Node)</li>
</ul>
<p>结点链接,成为一个链表,即为线性表的链式存储结构.</p>
<pre class="mermaid">
graph LR;
    subgraph 头指针
    A["head| · "]
    end
    B["a1| ·"]
    subgraph 结点
    C["a2(数据)| ·(指针)"]
    end
    D[...]
    E["an|null"]

    A-->B-->C-->D-->E</pre>

<p>最后一个节点指针为空</p>

        </div>

        

        
            <ul class="post-tags-box">
                
                    <li class="tag-item">
                        <a href="/tags/%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/">#学习笔记</a>&nbsp;
                    </li>
                
            </ul>
        

        

        
            <div class="article-nav">
                
                    <div class="article-prev">
                        <a class="prev"
                        rel="prev"
                        href="/2023/09/23/Python%E5%9F%BA%E7%A1%80/"
                        >
                            <span class="left arrow-icon flex justify-center items-center">
                                <i class="fa-solid fa-chevron-left"></i>
                            </span>
                            <span class="title flex justify-center items-center">
                                <span class="post-nav-title-item">Python基础</span>
                                <span class="post-nav-item">上一篇</span>
                            </span>
                        </a>
                    </div>
                
                
                    <div class="article-next">
                        <a class="next"
                        rel="next"
                        href="/2023/09/17/%E5%89%8D%E7%AB%AFWeb%E5%BC%80%E5%8F%91-HTML5-CSS-JS%E7%AC%94%E8%AE%B0/"
                        >
                            <span class="title flex justify-center items-center">
                                <span class="post-nav-title-item">前端Web开发(HTML5+CSS+JS笔记)</span>
                                <span class="post-nav-item">下一篇</span>
                            </span>
                            <span class="right arrow-icon flex justify-center items-center">
                                <i class="fa-solid fa-chevron-right"></i>
                            </span>
                        </a>
                    </div>
                
            </div>
        


        
    </div>

    
        <div class="toc-content-container">
            <div class="post-toc-wrap">
    <div class="post-toc">
        <div class="toc-title">此页目录</div>
        <div class="page-title">数据结构与算法(c语言)</div>
        <ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#%E7%AC%AC%E4%B8%80%E7%AB%A0-%E7%BB%AA%E8%AE%BA"><span class="nav-text">第一章 绪论</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E4%BB%80%E4%B9%88%E6%98%AF%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84"><span class="nav-text">什么是数据结构</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E4%BB%80%E4%B9%88%E6%98%AF%E7%AE%97%E6%B3%95"><span class="nav-text">什么是算法</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E7%AE%97%E6%B3%95%E7%9A%84%E5%9F%BA%E6%9C%AC%E7%89%B9%E5%BE%81"><span class="nav-text">算法的基本特征</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%92%8C%E7%A9%BA%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6"><span class="nav-text">时间复杂度和空间复杂度</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#%E7%AC%AC%E4%BA%8C%E7%AB%A0-%E7%BA%BF%E6%80%A7%E8%A1%A8"><span class="nav-text">第二章 线性表</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E7%BA%BF%E6%80%A7%E8%A1%A8%E7%9A%84%E5%AE%9A%E4%B9%89"><span class="nav-text">线性表的定义</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%8A%BD%E8%B1%A1%E6%95%B0%E6%8D%AE%E7%B1%BB%E5%9E%8B"><span class="nav-text">抽象数据类型</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E7%BA%BF%E6%80%A7%E8%A1%A8%E7%9A%84%E9%A1%BA%E5%BA%8F%E5%AD%98%E5%82%A8%E7%BB%93%E6%9E%84"><span class="nav-text">线性表的顺序存储结构</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E7%BA%BF%E6%80%A7%E8%A1%A8%E7%9A%84%E9%93%BE%E5%BC%8F%E5%AD%98%E5%82%A8%E7%BB%93%E6%9E%84"><span class="nav-text">线性表的链式存储结构</span></a></li></ol></li></ol>

    </div>
</div>
        </div>
    
</div>



                

            </div>

            

        </div>

        <div class="main-content-footer">
            <footer class="footer mt-5 py-5 h-auto text-base text-third-text-color relative border-t-2 border-t-border-color">
    <div class="info-container py-3 text-center">
        
            <div class="customize-info my-1">死亡是涅灭,抑或是永恒?</div>
        
        <div class="text-center">
            &copy;
            
              <span>2023</span>
              -
            
            2023&nbsp;&nbsp;<i class="fa-solid fa-heart fa-beat" style="--fa-animation-duration: 0.5s; color: #f54545"></i>&nbsp;&nbsp;<a href="/">雲之残骸</a>
        </div>
        
        <div class="relative text-center lg:absolute lg:left-[20px] lg:top-1/2 lg:-translate-y-1/2 lg:text-left">
            <span class="lg:block text-sm">由 <?xml version="1.0" encoding="utf-8"?><!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"><svg class="relative top-[2px] inline-block align-baseline" version="1.1" id="圖層_1" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" x="0px" y="0px" width="1rem" height="1rem" viewBox="0 0 512 512" enable-background="new 0 0 512 512" xml:space="preserve"><path fill="#0E83CD" d="M256.4,25.8l-200,115.5L56,371.5l199.6,114.7l200-115.5l0.4-230.2L256.4,25.8z M349,354.6l-18.4,10.7l-18.6-11V275H200v79.6l-18.4,10.7l-18.6-11v-197l18.5-10.6l18.5,10.8V237h112v-79.6l18.5-10.6l18.5,10.8V354.6z"/></svg><a target="_blank" class="text-base" href="https://hexo.io">Hexo</a> 驱动</span>
            <span class="text-sm lg:block">主题&nbsp;<a class="text-base" target="_blank" href="https://github.com/EvanNotFound/hexo-theme-redefine">Redefine v2.4.4</a></span>
        </div>
        
        
            <div>
                博客已运行 <span class="odometer" id="runtime_days" ></span> 天 <span class="odometer" id="runtime_hours"></span> 小时 <span class="odometer" id="runtime_minutes"></span> 分钟 <span class="odometer" id="runtime_seconds"></span> 秒
            </div>
        
        
            <script data-swup-reload-script>
                try {
                    function odometer_init() {
                    const elements = document.querySelectorAll('.odometer');
                    elements.forEach(el => {
                        new Odometer({
                            el,
                            format: '( ddd).dd',
                            duration: 200
                        });
                    });
                    }
                    odometer_init();
                } catch (error) {}
            </script>
        
        
        
    </div>  
</footer>
        </div>
    </div>

    
        <div class="post-tools">
            <div class="post-tools-container">
    <ul class="article-tools-list">
        <!-- TOC aside toggle -->
        
            <li class="right-bottom-tools page-aside-toggle">
                <i class="fa-regular fa-outdent"></i>
            </li>
        

        <!-- go comment -->
        
    </ul>
</div>

        </div>
    

    <div class="right-side-tools-container">
        <div class="side-tools-container">
    <ul class="hidden-tools-list">
        <li class="right-bottom-tools tool-font-adjust-plus flex justify-center items-center">
            <i class="fa-regular fa-magnifying-glass-plus"></i>
        </li>

        <li class="right-bottom-tools tool-font-adjust-minus flex justify-center items-center">
            <i class="fa-regular fa-magnifying-glass-minus"></i>
        </li>

        <li class="right-bottom-tools tool-expand-width flex justify-center items-center">
            <i class="fa-regular fa-expand"></i>
        </li>

        <li class="right-bottom-tools tool-dark-light-toggle flex justify-center items-center">
            <i class="fa-regular fa-moon"></i>
        </li>

        <!-- rss -->
        

        

        <li class="right-bottom-tools tool-scroll-to-bottom flex justify-center items-center">
            <i class="fa-regular fa-arrow-down"></i>
        </li>
    </ul>

    <ul class="visible-tools-list">
        <li class="right-bottom-tools toggle-tools-list flex justify-center items-center">
            <i class="fa-regular fa-cog fa-spin"></i>
        </li>
        
            <li class="right-bottom-tools tool-scroll-to-top flex justify-center items-center">
                <i class="arrow-up fas fa-arrow-up"></i>
                <span class="percent"></span>
            </li>
        
        
    </ul>
</div>

    </div>

    <div class="image-viewer-container">
    <img src="">
</div>


    
        <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
          <span class="search-input-field-pre">
            <i class="fa-solid fa-keyboard"></i>
          </span>
            <div class="search-input-container">
                <input autocomplete="off"
                       autocorrect="off"
                       autocapitalize="off"
                       placeholder="搜索..."
                       spellcheck="false"
                       type="search"
                       class="search-input"
                >
            </div>
            <span class="popup-btn-close">
                <i class="fa-solid fa-times"></i>
            </span>
        </div>
        <div id="search-result">
            <div id="no-result">
                <i class="fa-solid fa-spinner fa-spin-pulse fa-5x fa-fw"></i>
            </div>
        </div>
    </div>
</div>

    

</main>


    
<script src="/js/libs/Swup.min.js"></script>

<script src="/js/libs/SwupSlideTheme.min.js"></script>

<script src="/js/libs/SwupScriptsPlugin.min.js"></script>

<script src="/js/libs/SwupProgressPlugin.min.js"></script>

<script src="/js/libs/SwupScrollPlugin.min.js"></script>

<script>
    const swup = new Swup({
        plugins: [
            new SwupScriptsPlugin({
                optin: true,
            }),
            new SwupProgressPlugin(),
            new SwupScrollPlugin({
                offset: 80,
            }),
            new SwupSlideTheme({
                mainElement: ".main-content-body",
            }),
        ],
        containers: ["#swup"],
    });

    swup.hooks.on("page:view", () => {
        Global.refresh();
    });

    // if (document.readyState === "complete") {
    //
    // } else {
    //     document.addEventListener("DOMContentLoaded", () => init());
    // }
</script>






<script src="/js/utils.js" type="module"></script>

<script src="/js/main.js" type="module"></script>

<script src="/js/layouts/navbarShrink.js" type="module"></script>

<script src="/js/tools/scrollTopBottom.js" type="module"></script>

<script src="/js/tools/lightDarkSwitch.js" type="module"></script>

<script src="/js/layouts/categoryList.js" type="module"></script>



    
<script src="/js/tools/localSearch.js"></script>






    
<script src="/js/layouts/lazyload.js"></script>




    
<script src="/js/tools/runtime.js"></script>

    
<script src="/js/libs/odometer.min.js"></script>

    
<link rel="stylesheet" href="/assets/odometer-theme-minimal.css">




  
<script src="/js/libs/Typed.min.js"></script>

  
<script src="/js/plugins/typed.js"></script>




    
<script src="/js/libs/mermaid.min.js"></script>

    
<script src="/js/plugins/mermaid.js"></script>




    
<script src="/js/libs/minimasonry.min.js"></script>

    
<script src="/js/plugins/masonry.js" type="module"></script>




<div class="post-scripts" data-swup-reload-script>
    
        
<script src="/js/libs/anime.min.js"></script>

        
<script src="/js/tools/tocToggle.js" type="module"></script>

<script src="/js/layouts/toc.js" type="module"></script>

<script src="/js/plugins/tabs.js" type="module"></script>

    
</div>


</body>
</html>
